package com.tping.redis;

import java.util.*;

/**
 * 实现缓存清理策略:
 * LFU在一段时间内，数据被使用频次最少的，优先被淘汰（双维度：先次数、后时间）
 *
 * LRU是最近最少使用策略，判断最近被使用的时间，距离目前最远的数据优先被淘汰（单维度：使用时间）
 *
 */
public class LFU<K, V> {

    // 容量
    private int capacity;

    private Map<K, Node> caches;

    public LFU(int size){
        this.capacity = size;
        caches = new LinkedHashMap<K, Node>(size);
    }

    public Object get(K key){
        Node node = caches.get(key);
        if( node == null ) return null;
        node.count++;
        node.time = System.nanoTime();
        sort();  // 做一次排序
        return node.value;
    }

    public void put(K key, Object value){
        Node node = caches.get(key);
        if( node == null ){
            // 是否已经满了
            if( capacity <= caches.size() ){
                // 已满，则清楚count最小，time最小
                K k = remoteLastUseNode();
                caches.remove(k);
            }
            node = new Node(key, value, 1, System.nanoTime());
            caches.put(key, node);
        }else{
            node.value = value;
            node.count++;
            node.time = System.nanoTime();
        }
        sort();  // 做一次排序
    }

    /**
     * 排序
     */
    private void sort(){
        List<Map.Entry<K, Node>> list = new ArrayList<Map.Entry<K, Node>>(caches.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<K, Node>>() {
            @Override
            public int compare(Map.Entry<K, Node> o1, Map.Entry<K, Node> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });

        caches.clear();
        for (Map.Entry<K, Node> entry : list ){
            caches.put(entry.getKey(), entry.getValue());
        }
    }

    private K remoteLastUseNode() {
        Collection<Node> nodes = caches.values();
        Node min = Collections.min(nodes);
        return (K) min.key;
    }

    public int size(){
        return caches.size();
    }

    public Map<K, Node> getCaches(){
        return caches;
    }

    static class Node implements Comparable<Node>{

        Object key;
        Object value;

        int count;
        long time;

        Node(Object key, Object value, int count, long time) {
            this.key = key;
            this.value = value;
            this.count = count;
            this.time = time;
        }

        @Override
        public int compareTo(Node o) {
            int compare;
            return ((compare = Integer.compare(this.count, o.count)) == 0
                    ? Long.compare(this.time, o.time)
                    : compare);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", count=" + count +
                    ", time=" + time +
                    '}';
        }
    }

}
